package LeetCode;

import java.util.*;

public class LC_218_TheSkylineProblem {

    public static void main(String[] args) {

    }

    static class Solution {

        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> res = new ArrayList<>();
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11, (a, b) -> b - a);
            List<int[]> bl = new ArrayList<>();
            for (int[] building : buildings) {
                bl.add(new int[]{building[0], building[2]});
                bl.add(new int[]{building[1], -building[2]});
            }
            bl.sort((a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
            int pre = 0, cur;
            for (int[] b : bl) {
                if (b[1] > 0) {
                    maxHeap.add(b[1]);
                    cur = maxHeap.peek();
                } else {
                    maxHeap.remove(-b[1]);
                    cur = (maxHeap.peek() == null) ? 0 : maxHeap.peek();
                }
                if (cur != pre) {
                    res.add(new int[]{b[0], cur});
                    pre = cur;
                }
            }
            return res;
        }

    }
}